package com.atfcm.stack;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Objects;

/**
 * @Author 96534
 * @create 2025/3/27 14:29
 */
public class T_496_下一个更大元素 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> num1Map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            num1Map.put(nums1[i], i);
        }
        int[] res = new int[nums1.length];
        Deque<Integer> stack = new LinkedList<>();
        for(int j = 0; j < nums2.length; j++) {
            while (!stack.isEmpty() && stack.peek() < nums2[j]) {
                Integer pop = stack.pop();
                Integer i = num1Map.remove(pop);
                if(Objects.nonNull(i)){
                    res[i] = nums2[j];
                }
            }
            stack.push(nums2[j]);
        }
        num1Map.values().forEach(i -> res[i] = -1);
        return res;
    }
}
